package com.study.binary;

import java.util.Arrays;
import java.util.List;

/**
 * 二分查找：前提是有序的数组
 *
 * @author yyb8152
 * @since 20220822
 **/
public class SearchBinary {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(4, 5, 10, 300);
        System.out.println(binarySearch(list, 300));

    }

    public static Integer binarySearch(List<Integer> list, Integer item) {
        int low = 0;
        int high = list.size() - 1;
        int mid, guess;

        // 只要范围没有缩小到只包含一个元素
        while (low <= high) {
            // 就检查中间的数（折半）
            mid = (low + high) / 2;
            // 猜中间的数
            guess = list.get(mid);
            // 找到了元素
            if (guess == item) {
                return mid;
            }
            // 猜到了
            if (guess > item) {
                high = mid - 1;
            } else {
                // 猜小了
                low = mid + 1;
            }

        }
        return null;
    }

}
